package main

import "fmt"

type node struct {
	left    *node
	mid     *node
	right   *node
	dataOne int
	dataTwo int

	parent *node
}

func (n *node) insert(data int) {

	// 空tree
	//fmt.Println("====")
	//fmt.Println(n)
	if n.dataOne == 0 {
		//if n.parent == nil {
		n.dataOne = data
		//} else {
		//	temp := new(node)
		//	temp.parent = n
		//	temp.dataOne = data
		//	n.left = temp
		//}

		return
	}

	diff := data < n.dataOne

	// leaf
	if n.left == nil && n.mid == nil && n.right == nil {
		// 只有dataOne
		if n.dataTwo == 0 {

			if diff {
				n.dataTwo = n.dataOne
				n.dataOne = data
			} else {
				n.dataTwo = data
			}

		} else {
			n.splitLeaf(data)

			if n.parent != nil {
				n.parent.pushUp(n)
			}
		}

		return
	}

	// not a leaf
	if diff {
		n.left.insert(data)
	} else {
		if n.dataTwo == 0 || data < n.dataTwo {
			n.mid.insert(data)
		} else {
			n.right.insert(data)
		}

	}

	//// 空tree
	//if n.dataOne == nil {
	//	n.dataOne = &data;
	//	return
	//}
	//
	//diff := data > *n.dataOne
	//
	////只有dataOne
	//if n.left == nil && n.mid == nil && n.right == nil {
	//	if n.dataTwo == nil {
	//
	//		if diff {
	//			n.dataTwo = &data
	//		} else {
	//			n.dataTwo = n.dataOne
	//			n.dataOne = &data
	//		}
	//	} else {
	//		n.splitLeaf(data)
	//
	//		if n.parent != nil {
	//			n.parent.pushUp(n);
	//		}
	//	}
	//}
	//
	//// not a leaf
	//if !diff {
	//	n.left.insert(data, n)
	//} else if n.dataTwo == nil {
	//	n.mid.insert(data, n)
	//} else {
	//
	//}

}

func (n *node) splitLeaf(data int) {

	if data < n.dataOne {
		leftNode := new(node)
		leftNode.dataOne = data
		leftNode.parent = n
		n.left = leftNode

		midNode := new(node)
		midNode.dataOne = n.dataTwo
		midNode.parent = n
		n.mid = midNode

	} else if data > n.dataOne && data < n.dataTwo {
		leftNode := new(node)
		leftNode.dataOne = n.dataOne
		leftNode.parent = n
		n.left = leftNode

		midNode := new(node)
		midNode.dataTwo = n.dataTwo
		midNode.parent = n
		n.mid = midNode

		n.dataOne = data
	} else {
		leftNode := new(node)
		leftNode.dataOne = n.dataOne
		leftNode.parent = n
		n.left = leftNode

		midNode := new(node)
		midNode.dataTwo = data
		midNode.parent = n
		n.mid = midNode

		n.dataOne = n.dataTwo
	}

	n.dataTwo = 0
}

func (n *node) pushUp(child *node) {

	diff := child.dataOne < n.dataOne
	// 一元素
	if n.dataTwo == 0 {

		if diff {

			n.dataTwo = n.dataOne
			n.dataOne = child.dataOne
			n.left = child.left
			n.right = n.mid
			n.mid = child.mid
			n.left.parent = n
			n.mid.parent = n

		} else {
			n.dataTwo = child.dataOne
			n.mid = child.left
			n.right = child.right
			n.mid.parent = n
			n.right.parent = n
		}
	} else {
		n.splitThreeNode(child)

		if n.parent != nil {
			n.parent.pushUp(n)
		}
	}

}

func (n *node) splitThreeNode(child *node) {


	diff := child.dataOne < n.dataOne



	if diff {
		tempMid := new(node)
		tempMid.parent = n
		tempMid.dataOne = n.dataTwo
		tempMid.left = n.mid
		tempMid.mid = n.right
		n.right = nil

		n.dataTwo = 0
		n.mid = tempMid

	} else if !diff && child.dataOne < n.dataTwo {


		tempLeft := new(node)
		tempLeft.parent = n
		tempLeft.dataOne = n.dataOne
		tempLeft.left = n.left
		tempLeft.mid = child.left

		tempMid := new(node)
		tempMid.parent = n
		tempMid.dataOne = n.dataTwo
		tempMid.left = child.mid
		tempMid.mid = n.right

		n.dataOne = child.dataOne
		n.left = tempLeft
		n.mid = tempMid

		n.dataTwo = 0
		n.right = nil


	} else {
		tempLeft := new(node)
		tempLeft.parent = n
		tempLeft.dataOne = n.dataOne
		tempLeft.left = n.left
		tempLeft.mid = n.mid

		n.dataOne = n.dataTwo
		n.left = tempLeft
		n.mid = child

		n.right = nil
	}

}

func (n *node) traversal() {

	fmt.Printf("%p %v ", n, n)
	fmt.Println()

	if n.left != nil {
		n.left.traversal()
	}

	if n.mid != nil {
		n.mid.traversal()
	}

	if n.right != nil {
		n.right.traversal()
	}
}


func main() {


	//arr := [...]int{55, 50, 45}
	//arr := [...]int{42, 37, 12, 18, 6, 11, 5}


	arr := [...]int{42, 37, 12, 18, 6, 10, 11}

	root := new(node)
	for i := 0; i < len(arr); i++ {
		root.insert(arr[i])
	}

	root.traversal()

}
